public class lianXuZuiDaHe {
    /**
     * 输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，
     * 子数组最小长度为1。求所有子数组的和的最大值
     * 输入：[1,-2,3,10,-4,7,2,-5]
     * 返回值：18
     * 说明：经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18
     */
    public int FindGreatestSumOfSubArray(int[] array) {
        int[] dp = new int[array.length];
        int max = array[0];
        dp[0] = array[0];
        for (int i = 1; i <array.length; i++) {
            dp[i] = Math.max(dp[i-1] + array[i],array[i]);
            max = Math.max(dp[i],max);
        }
        return max;
    }
    public int FindGreatestSumOfArrat2(int[] array) {
        int sum = 0;
        int max = array[0];
        for (int i = 0; i < array.length ; i++) {
            sum = Math.max(sum + array[i],array[i]);
            max = Math.max(sum,max);
        }
        return max;
    }
}
